package class10;

import java.util.HashSet;
import java.util.Stack;

/**
 *
 * 深度优先遍历
 * 1.利用栈实现
 * 2.从源节点开始把节点按照深度放入栈,然后弹出
 * 3.每弹出一个点, 把该节点下一个没有进过栈的邻接点放入栈
 * 4.直到栈变空
 *
 */
public class Code02_DFS {

	public static void dfs(Node node) {
		if (node == null) {
			return;
		}
		//栈, 实际记录的是深度遍历的路径
		Stack<Node> stack = new Stack<>();
		//保证不重复进入
		HashSet<Node> set = new HashSet<>();
		//先压入深度遍历的出发点
		stack.add(node);
		set.add(node);
		System.out.println(node.value);
		while (!stack.isEmpty()) {
			//弹出节点, 并获取节点是否具有下个节点
			Node cur = stack.pop();
			for (Node next : cur.nexts) {
				//判断下个节点是否已经走过
				if (!set.contains(next)) {
					//没有走过则把当前节点和下个节点逐步压入
					//即:栈中保留了整条从开始节点出发的深度路径
					stack.push(cur);
					stack.push(next);
					set.add(next);
					System.out.println(next.value);
					//不再寻找宽度的next, 而是跳出, 去找next的next了
					//宽度的next可以在一条深度走到路的尽头后, 通过栈弹出进行回退深度, 然后在while继续遍历宽度
					break;
				}
			}
		}
	}

}
